Những liên hệ đầu tiên của họ có niên đại vào thế kỷ 19 khi Đế quốc Anh đang chú ý đến các nước thuộc địa ở châu Á, thì thực dân Pháp sau đó đã từ chối tiếp xúc chính thức giữa Việt Nam và Úc. Cho đến khi kết thúc Thế chiến II, quan hệ giữa Úc và Việt Nam gần như không tồn tại.

Chiến tranh Việt Nam

Nỗi sợ hãi sau đó của chủ nghĩa cộng sản đã lôi kéo Úc đến trước chiến tranh Việt Nam, trong đó Úc tham gia như một phần của sự can thiệp chống cộng vào Việt Nam để hỗ trợ Nam Việt Nam chống lại Bắc Việt Nam. Úc cam kết gửi 50.000 quân chống lại cộng sản, trong đó 520 người đã thiệt mạng. Chiến tranh đã ảnh hưởng sâu sắc đến xã hội Úc.

Sau khi Chiến tranh Việt Nam kết thúc, Úc đã tiếp đón nhiều người tị nạn Việt Nam chạy trốn khỏi sự sụp đổ kinh tế do chiến tranh. Người tị nạn Việt Nam là nhóm lớn người di cư không phải người châu Âu đầu tiên vào Úc sau khi loại bỏ chính sách của ''Úc trắng''.